package main.java.indi.zyj.coderecord;

import java.util.ArrayList;

public class KMP {


    public int strStr(String haystack, String needle) {

        int m = haystack.length();
        int n = needle.length();
        int[] next = new int[n];
        getNext(next, needle);

        int j = 0;

        for (int i = 0; i < m; i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) {
                j = next[j - 1];
            }
            if (needle.charAt(j) == haystack.charAt(i)) {
                j++;
            }
            if (j == n) {
                return i - j + 1;
            }
        }

        return -1;


    }



    public void getNext(int[] next, String s) {

        int j = 0;
        next[0] = 0;

        for (int i = 1; i < s.length(); i++) {
            while (s.charAt(i) != s.charAt(j) && j > 0) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }

    }

}
